package dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class LC354 {
    //动归+二分查找
    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes.length == 0) return 0;
        Arrays.sort(envelopes,new Comparator<int[]>(){
            public int compare(int[] a,int[] b){
                return a[0]==b[0]?b[1]-a[1]:a[0]-b[0];
            }
        });
        List<Integer> list=new ArrayList<>();
        list.add(envelopes[0][1]);
        for(int i=1;i<envelopes.length;i++){
            int num=envelopes[i][1];
            if(num>list.get(list.size()-1)){
                list.add(num);
            }else{
                int index=binarySearch(list,num);
                list.set(index,num);
            }
        }
        return list.size();
    }

    private int binarySearch(List<Integer> list,int target){
        int low=0;
        int high=list.size()-1;
        while(low<high){
            int mid=(high-low)/2+low;
            if(list.get(mid)<target){
                low=mid+1;
            }else{
                high=mid;
            }
        }
        return low;
    }
}



//暴力动归 现在的LC会超时
//        public int maxEnvelopes(int[][] envelopes) {
//                Arrays.sort(envelopes,new Comparator<int[]>(){
//                    public int compare(int[] a,int[] b){
//                        return a[0]==b[0]?b[1]-a[1]:a[0]-b[0];
//                    }
//                });
//                //对高度数组寻找最长递增子序列
//                int[] height=new int[envelopes.length];
//                for(int i=0;i<envelopes.length;i++){
//                    height[i]=envelopes[i][1];
//                }
//                return length(height);
//            }
//
//            //暴力动归
//            private int length(int[] height){
//                int[] dp=new int[height.length];
//                Arrays.fill(dp,1);
//                for(int i=0;i<height.length;i++){
//                    for(int j=0;j<i;j++){
//                        if(height[i]>height[j]){
//                            dp[i]=Math.max(dp[i],dp[j]+1);
//                        }
//                    }
//                }
//                int res=0;
//                for(int i=0;i<dp.length;i++){
//                    res=Math.max(res,dp[i]);
//                }
//                return res;
//
//        }





